package demo;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *  1.完成3个快速排序方法并且写出快速排序的优化方法
 *  2.完成快速排序非递归版
 *  3.完成归并排序
 *  4.完成归并排序非递归版本
 *  5.完成计数排序
 * User: 石方旭
 * Date: 2022-06-20
 * Time: 15:00
 */
public class TestDemo {

    //交换函数
    public static void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //插入排序用来优化快速排序
    public static void InsertSort(int[] nums,int left,int right){
        for(int i =left;i<=right;++i){
            int tmp =nums[i];
            int j = i-1;
            for(;j>=0;j--){
                if(nums[j]>tmp){
                    nums[j+1] = nums[j];
                }else {
                    break;
                }
            }
            nums[j+1] = tmp;
        }
    }

    //hoare法
    public static int hoarePartition(int[] nums,int left,int right){
        //思路left为基准，左边开始找
        //右边找比基准元素小的，左边找比基准元素大的，然后进行交换
        int standard = left;//基准元素
        while(left<right){
            //右边找小
            while(left<right&&nums[standard]<=nums[right]){
                right--;
            }
            //左边找大
            while(left<right&&nums[standard]>=nums[left]){
                left++;
            }
            swap(nums,left,right);
        }
        //此时left和right相遇这个位置就是基准元素的位置
        swap(nums,left,standard);
        return left;
    }

    //挖坑法
    public static int holePartition(int[] nums,int left,int right){
        //思路左边挖坑(基准元素)右边找小埋上,右边挖坑左边找大埋上
        int pivot = nums[left];
        while(left<right){
            //右边找小
            while(left<right&&nums[right]>=pivot){
                right--;
            }
            nums[left] = nums[right];
            while(left<right&&nums[left]<=pivot){
                left++;
            }
            nums[right] = nums[left];
        }
        //此时left和right是相遇的
        nums[left] = pivot;
        return left;
    }

    //前后指针法
    public static int pointerPartition(int[] nums,int left,int right){
        //定义两个指针 cur负责找比pivot小的元素，然后++prev就是大的元素，cur与prev进行交换
        int prev = left;
        int cur = left+1;
        int pivot = left;
        while(cur<=right){
            if(nums[pivot]>nums[cur]&& +prev!=cur){
                swap(nums,cur,prev);
            }
            cur++;
        }
        swap(nums,prev,pivot);
        return prev;
    }

    //三数取中
    public static int middleOfThree(int[] nums,int left,int right){
          int mid = left+(right-left)>>>1;
          if(nums[left]<nums[right]){
              if(nums[left]<nums[mid]){
                  return mid;
              }else if(nums[mid]>nums[right]){
                  return right;
              }else {
                  return left;
              }
          }else {
              if(nums[mid]>nums[right]){
                  return mid;
              }else if(nums[mid]>nums[left]){
                  return left;
              }else {
                  return right;
              }
          }
    }

    public static void quickSort(int[] nums,int left,int right){
        if(left>=right){
            return;
        }
        if((left-right+1)<=10000){
            InsertSort(nums,left,right);
            return;
        }
        //趋近于有序利用三数取中法优化更好
        int index = middleOfThree(nums,left,right);
        swap(nums,left,index);
        int mid = pointerPartition(nums,left,right);
        quickSort(nums,left,mid-1);
        quickSort(nums,mid+1,right);
    }

    //快速排序非递归版本
    public static void QuickSortNorN(int[] nums,int left,int right){
         Stack<Integer> stack = new Stack<>();
         int mid = holePartition(nums,left,right);
         if(left<mid-1){
            stack.push(left);
            stack.push(mid-1);
         }
         if(right>mid+1){
             stack.push(mid+1);
             stack.push(right);
         }
         while(!stack.isEmpty()){
             right = stack.pop();
             left = stack.pop();
             mid = holePartition(nums,left,right);
             if(left<mid-1){
                 stack.push(left);
                 stack.push(mid-1);
             }
             if(right>mid+1){
                 stack.push(mid+1);
                 stack.push(right);
             }
         }
    }

    public static void QuickSortNor(int[] nums,int left,int right){
         Stack<Integer> stack = new Stack<>();
         int mid = pointerPartition(nums,left,right);
         if(left<mid-1){
             stack.push(left);
             stack.push(mid-1);
         }
         if(right>mid+1){
             stack.push(mid+1);
             stack.push(right);
         }
         while(!stack.isEmpty()){
             right = stack.pop();
             left = stack.pop();
             mid = pointerPartition(nums,left,right);
             if(left<mid-1){
                 stack.push(left);
                 stack.push(mid-1);
             }
             if(right>mid+1){
                 stack.push(mid+1);
                 stack.push(right);
             }
         }
    }

    public static void MergeSort(int[] nums,int left,int mid,int right){
         int s1 = left;
         int e1 = mid;
         int s2 = mid+1;
         int e2 = right;
         //开始合并
        int k =0;
        int[] tmp = new int[nums.length];
        while(s1<=e1&&s2<=e2){
            if(nums[s1]>nums[s2]){
                tmp[k++] = nums[s2++];
            }else {
                tmp[k++] = nums[s1++];
            }
        }
        while(s1<=e1){
            tmp[k++] = nums[s1++];
        }
        while(s2<=e2){
            tmp[k++] = nums[s2++];
        }
        //拷贝回原数组
        for(int i =0;i<k;++i){
            nums[i+left] = tmp[i];
        }

    }
    //归并排序
    public static void merge(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }
      int mid =(left+right)>>>1;
      //分解
      merge(nums,left,mid);
      merge(nums,mid+1,right);
      MergeSort(nums,left,mid,right);

    }

    //归并排序非递归版本
    public static void MergeSortNor(int[] nums,int left,int right){
        int gap =1;
        int mid =(left+right)>>>1;
        while(gap<nums.length){
            for(int i =0;i<nums.length;i+=2*gap){
                left =i;
                //1 2 3 4
                mid = left+gap-1;
                //修正mid
                if(mid>=nums.length){
                    mid= nums.length-1;
                }
                right = mid+gap;
                if(right>=nums.length){
                    right= nums.length-1;
                }
                MergeSort(nums,left,mid,right);
            }
            gap*=2;
        }

    }

    //计数排序
    public static int[] CountRangeSort1(int[] nums){
        //求数组中的最大值和最小值
        int max = nums[0];
        int min = nums[0];
        for(int i =1;i<nums.length;++i){
            if(nums[i]>max){
                max = nums[i];
            }
            if(nums[i]<min){
                min = nums[i];
            }
        }       //此时求得最大值和最小值
        //开始对数组中的每一个数字进行计数
        int[] count = new int[max-min+1];
        for(int i =0;i<nums.length;++i){
            count[nums[i]-min]++;
        }
        int[] tmp = new int[nums.length];
        //计数完成开始将每个数字按计数顺序进行全部打印出来
        int index =0;
        for(int j =0;j<count.length;++j){
            while(count[j]>0){
                tmp[index++]= j+min;
                count[j]--;
            }
        }
        return tmp;
    }

    public static int[] CountRangeSort(int[] nums){
        //找出数组中的最大值和最小值
        int max = nums[0];
        int min = nums[0];
        for(int i =1;i<nums.length;++i){
            if(nums[i]>max){
                max = nums[i];
            }
            if(nums[i]<min){
                min = nums[i];
            }
        }
        //对计数数组开始计数
        int[] count = new int[max-min+1];
        for(int i =0;i<nums.length;++i){
            count[nums[i]-min]++;
        }
        int[] tmp = new int[nums.length];
        int index =0;
        for(int j =0;j<count.length;++j){
            while(count[j]>0){
                tmp[index++] = j+min;
                count[j]--;
            }
        }
        return tmp;
    }


    public static void main(String[] args) {
         int[] nums = {9,9,9,9,5,6,5,2,3,4,1,5,6,6,0,0,0,10};
        int[] tmp =CountRangeSort(nums);
         System.out.println(Arrays.toString(tmp));
    }
}
